package com.ry.day1129;

public class LC141 {

    static class Solution {
        /**
         * @param x: An integer
         * @return: The sqrt of x
         */
        public int sqrt(int x) {
            if(x <2 ) return x;
            long L=1;
            long R = x/2;
            while (L<R){
                long m = (L+R)/2;
                if(m*m <=x && (m+1) *(m+1)>x){
                    return (int)m;
                }else if(m> x/m) {
                    R=m-1;
                }else{
                    L=m+1;
                }
            }

            return (int) L;
        }
    }


    public static void main(String[] args) {
        System.out.println(new Solution().sqrt(0));
        System.out.println(new Solution().sqrt(3));
        System.out.println(new Solution().sqrt(4));
    }
}
